package com.sheng.leetcode.year2025.month09.day20;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2025/9/22
 * <p>
 * 3508. 设计路由器<p>
 * <p>
 * 请你设计一个数据结构来高效管理网络路由器中的数据包。每个数据包包含以下属性：<p>
 * source：生成该数据包的机器的唯一标识符。<p>
 * destination：目标机器的唯一标识符。<p>
 * timestamp：该数据包到达路由器的时间戳。<p>
 * 实现 Router 类：<p>
 * Router(int memoryLimit)：初始化路由器对象，并设置固定的内存限制。<p>
 * memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。<p>
 * 如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。<p>
 * bool addPacket(int source, int destination, int timestamp)：将具有给定属性的数据包添加到路由器。<p>
 * 如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。<p>
 * 如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。<p>
 * int[] forwardPacket()：以 FIFO（先进先出）顺序转发下一个数据包。<p>
 * 从存储中移除该数据包。<p>
 * 以数组 [source, destination, timestamp] 的形式返回该数据包。<p>
 * 如果没有数据包可以转发，则返回空数组。<p>
 * int getCount(int destination, int startTime, int endTime)：<p>
 * 返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。<p>
 * 注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。<p>
 * <p>
 * 示例 1：<p>
 * 输入：<p>
 * ["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]<p>
 * [[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]<p>
 * 输出：<p>
 * [null, true, true, false, true, true, [2, 5, 90], true, 1]<p>
 * 解释：<p>
 * Router router = new Router(3); // 初始化路由器，内存限制为 3。<p>
 * router.addPacket(1, 4, 90); // 数据包被添加，返回 True。<p>
 * router.addPacket(2, 5, 90); // 数据包被添加，返回 True。<p>
 * router.addPacket(1, 4, 90); // 这是一个重复数据包，返回 False。<p>
 * router.addPacket(3, 5, 95); // 数据包被添加，返回 True。<p>
 * router.addPacket(4, 5, 105); // 数据包被添加，[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。<p>
 * router.forwardPacket(); // 转发数据包 [2, 5, 90] 并将其从路由器中移除。<p>
 * router.addPacket(5, 2, 110); // 数据包被添加，返回 True。<p>
 * router.getCount(5, 100, 110); // 唯一目标地址为 5 且时间在 [100, 110] 范围内的数据包是 [4, 5, 105]，返回 1。<p>
 * <p>
 * 示例 2：<p>
 * 输入：<p>
 * ["Router", "addPacket", "forwardPacket", "forwardPacket"]<p>
 * [[2], [7, 4, 90], [], []]<p>
 * 输出：<p>
 * [null, true, [7, 4, 90], []]<p>
 * 解释：<p>
 * Router router = new Router(2); // 初始化路由器，内存限制为 2。<p>
 * router.addPacket(7, 4, 90); // 返回 True。<p>
 * router.forwardPacket(); // 返回 [7, 4, 90]。<p>
 * router.forwardPacket(); // 没有数据包可以转发，返回 []。<p>
 * <p>
 * 提示：<p>
 * 2 <= memoryLimit <= 10^5<p>
 * 1 <= source, destination <= 2 * 10^5<p>
 * 1 <= timestamp <= 10^9<p>
 * 1 <= startTime <= endTime <= 10^9<p>
 * addPacket、forwardPacket 和 getCount 方法的总调用次数最多为 10^5。<p>
 * 对于 addPacket 的查询，timestamp 按递增顺序给出。<p>
 */
public class LeetCode3508 {

    @Test
    public void test() {
        // 初始化路由器，内存限制为 3。
        Router router = new Router(3);
        // 数据包被添加，返回 True。
        System.out.println(router.addPacket(1, 4, 90));
        // 数据包被添加，返回 True。
        System.out.println(router.addPacket(2, 5, 90));
        // 这是一个重复数据包，返回 False。
        System.out.println(router.addPacket(1, 4, 90));
        // 数据包被添加，返回 True。
        System.out.println(router.addPacket(3, 5, 95));
        // 数据包被添加，[1, 4, 90] 被移除，因为数据包数量超过限制，返回 True。
        System.out.println(router.addPacket(4, 5, 105));
        // 转发数据包 [2, 5, 90] 并将其从路由器中移除。
        router.forwardPacket();
        // 数据包被添加，返回 True。
        System.out.println(router.addPacket(5, 2, 110));
        // 唯一目标地址为 5 且时间在 [100, 110] 范围内的数据包是 [4, 5, 105]，返回 1。
        System.out.println(router.getCount(5, 100, 110));
    }
}

/**
 * source：生成该数据包的机器的唯一标识符。
 * destination：目标机器的唯一标识符。
 * timestamp：该数据包到达路由器的时间戳。
 */
class Packet {
    private int source;
    private int destination;
    private int timestamp;

    public Packet(int source, int destination, int timestamp) {
    }

    @Override
    public boolean equals(Object obj) {
        return super.equals(obj);
    }
}

class Router {

    private int lim;

    private Set<Long> vis = new HashSet<>();

    private Deque<int[]> q = new ArrayDeque<>();

    private Map<Integer, Integer> idx = new HashMap<>();

    private Map<Integer, List<Integer>> d = new HashMap<>();

    /**
     * 初始化路由器对象，并设置固定的内存限制。
     *
     * @param memoryLimit 是路由器在任意时间点可以存储的 最大 数据包数量。
     *                    如果添加一个新数据包会超过这个限制，则必须移除 最旧的 数据包以腾出空间。
     */
    public Router(int memoryLimit) {
        this.lim = memoryLimit;
    }

    /**
     * 将具有给定属性的数据包添加到路由器。
     * 如果路由器中已经存在一个具有相同 source、destination 和 timestamp 的数据包，则视为重复数据包。
     * 如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。
     *
     * @param source
     * @param destination
     * @param timestamp
     * @return boolean 如果数据包成功添加（即不是重复数据包），返回 true；否则返回 false。
     */
    public boolean addPacket(int source, int destination, int timestamp) {
        long x = f(source, destination, timestamp);
        if (vis.contains(x)) {
            return false;
        }
        vis.add(x);
        if (q.size() >= lim) {
            forwardPacket();
        }
        q.offer(new int[]{source, destination, timestamp});
        d.computeIfAbsent(destination, k -> new ArrayList<>()).add(timestamp);
        return true;
    }

    /**
     * 以 FIFO（先进先出）顺序转发下一个数据包。
     * 从存储中移除该数据包。
     * 以数组 [source, destination, timestamp] 的形式返回该数据包。
     * 如果没有数据包可以转发，则返回空数组。
     *
     * @return
     */
    public int[] forwardPacket() {
        if (q.isEmpty()) {
            return new int[]{};
        }
        int[] packet = q.poll();
        int s = packet[0], d_ = packet[1], t = packet[2];
        vis.remove(f(s, d_, t));
        idx.merge(d_, 1, Integer::sum);
        return new int[]{s, d_, t};
    }

    private long f(int a, int b, int c) {
        return ((long) a << 46) | ((long) b << 29) | (long) c;
    }

    /**
     * 返回当前存储在路由器中（即尚未转发）的，且目标地址为指定 destination 且时间戳在范围 [startTime, endTime]（包括两端）内的数据包数量。
     * 注意：对于 addPacket 的查询会按照 timestamp 的递增顺序进行。
     *
     * @param destination 目标地址
     * @param startTime   该数据包到达路由器的时间戳开始时间
     * @param endTime     该数据包到达路由器的时间戳结束时间
     * @return 数量
     */
    public int getCount(int destination, int startTime, int endTime) {
        List<Integer> ls = d.getOrDefault(destination, Collections.emptyList());
        int k = idx.getOrDefault(destination, 0);
        int i = lowerBound(ls, startTime, k);
        int j = lowerBound(ls, endTime + 1, k);
        return j - i;
    }

    private int lowerBound(List<Integer> list, int target, int fromIndex) {
        int l = fromIndex, r = list.size();
        while (l < r) {
            int m = (l + r) >>> 1;
            if (list.get(m) < target) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }
}

/**
 * Your Router object will be instantiated and called as such:
 * Router obj = new Router(memoryLimit);
 * boolean param_1 = obj.addPacket(source,destination,timestamp);
 * int[] param_2 = obj.forwardPacket();
 * int param_3 = obj.getCount(destination,startTime,endTime);
 */

//class Router {
//    private record Packet(int source, int destination, int timestamp) {}
//
//    private static class Pair {
//        List<Integer> timestamps;
//        int head;
//        Pair() {
//            this.timestamps = new ArrayList<>();
//            this.head = 0;
//        }
//    }
//
//    private final int memoryLimit;
//    private final Queue<Packet> packetQ = new ArrayDeque<>();
//    private final Set<Packet> packetSet = new HashSet<>();
//    private final Map<Integer, Pair> destToTimestamps = new HashMap<>();
//
//    public Router(int memoryLimit) {
//        this.memoryLimit = memoryLimit;
//    }
//
//    public boolean addPacket(int source, int destination, int timestamp) {
//        Packet packet = new Packet(source, destination, timestamp);
//        if (!packetSet.add(packet)) return false;
//        if (packetQ.size() == memoryLimit) forwardPacket();
//        packetQ.add(packet);
//        destToTimestamps.computeIfAbsent(destination, k -> new Pair())
//                        .timestamps.add(timestamp);
//        return true;
//    }
//
//    public int[] forwardPacket() {
//        if (packetQ.isEmpty()) return new int[]{};
//        Packet packet = packetQ.poll();
//        packetSet.remove(packet);
//        Pair p = destToTimestamps.get(packet.destination);
//        p.head++;
//        return new int[]{packet.source, packet.destination, packet.timestamp};
//    }
//
//    public int getCount(int destination, int startTime, int endTime) {
//        Pair p = destToTimestamps.get(destination);
//        if (p == null) return 0;
//        int left = lowerBound(p.timestamps, startTime, p.head);
//        int right = lowerBound(p.timestamps, endTime + 1, p.head);
//        return right - left;
//    }
//
//    private int lowerBound(List<Integer> nums, int target, int left) {
//        int right = nums.size();
//        while (left < right) {
//            int mid = (left + right) >>> 1;
//            if (nums.get(mid) >= target) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return right;
//    }
//}
//
//作者：力扣官方题解
//链接：https://leetcode.cn/problems/implement-router/solutions/3772883/she-ji-lu-you-qi-by-leetcode-solution-hgxc/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
